//地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一
//格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但
//它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？ 
//
// 
//
// 示例 1： 
//
// 输入：m = 2, n = 3, k = 1
//输出：3
// 
//
// 示例 2： 
//
// 输入：m = 3, n = 1, k = 0
//输出：1
// 
//
// 提示： 
//
// 
// 1 <= n,m <= 100 
// 0 <= k <= 20 
// 
// Related Topics 深度优先搜索 广度优先搜索 动态规划 👍 515 👎 0

package leetcode.editor.cn;

import java.util.LinkedList;
import java.util.Queue;

//leetcode submit region begin(Prohibit modification and deletion)
class SolutionOffer13 {

    /**
     * 广度优先搜索,该代码太复杂，可以优化
     * @param m
     * @param n
     * @param k
     * @return
     */
    public int movingCount(int m, int n, int k){
        boolean[][] visited = new boolean[m][n];
        int result = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0,0});
        result++;
        visited[0][0] = true;
        while(!queue.isEmpty()){
            int[] arr = queue.poll();
            if(calSum(arr[0]) + calSum(arr[1]) > k){
                result--;
                continue;
            }
            if(arr[0]+1 < m && !visited[arr[0]+1][arr[1]]){
                queue.offer(new int[]{arr[0]+1,arr[1]});
                result++;
                visited[arr[0]+1][arr[1]] = true;

            }
            if(arr[1]+1 < n && !visited[arr[0]][arr[1]+1]){
                queue.offer(new int[]{arr[0],arr[1]+1});
                result++;
                visited[arr[0]][arr[1]+1] = true;
            }
        }
        return result;
    }

    /**
     * 深度优先搜索
     */
    int result = 0;
    int[][] board = null;
    public int movingCount1(int m, int n, int k) {
        board = new int[m][n];
        dfs(m, n, 0, 0, k);
        return result;
    }

    public void dfs(int m, int n, int i, int j, int k) {
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] == -1 ||calSum(i) + calSum(j) > k) {
            return;
        }
        result++;
        board[i][j] = -1;
        dfs(m, n, i + 1, j, k);
//        dfs(m, n, i - 1, j, k); //这里不需要，只向右和向下搜索，加上也没错
        dfs(m, n, i, j + 1, k);
//        dfs(m, n, i, j - 1, k);//这里不需要，只向右和向下搜索，加上也没错
        //这里不需要否则结果一直是0
        //result--;
        //这里也不需要，访问过了就一直标记为访问过，否则回溯的过程中可能出现重复访问
        //board[i][j] = 0;
    }

    public int calSum(int m) {
        int sum = 0;
        while (m > 0) {
            sum += m % 10;
            m /= 10;
        }
        return sum;
    }

    public static void main(String[] args) {
//        new Solution().movingCount(1,2,1);
        new SolutionOffer13().movingCount(3,1,11);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
